#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m;
ll ans;
bool s[6];
bool edge[6][6];
bool tmp[6][6];
bool ds[6];
bool can() {
	ll fd = 0;
	memset(ds, 0, sizeof ds);
	for (int i = 1; i <= n; i++) {
		if (s[i]) {
			fd++;
			ll r = 0;
			for (int j = 1; j <= n; j++)
				if (s[i] && s[j] && edge[i][j])
					r++;
			if (r > 1) {
				return 0;
			}
		}
	}
	ll rds = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i]) {
			ll cnt = 100;
			ds[i] = 1, rds++;
			while (cnt--) {
				ll d = i;
				for (int j = 1; j <= n; j++)
					if (edge[d][j]) {
						d = j;
						if (ds[j] == 0)
							ds[j] = 1, rds++;
					}
				if (d == i && fd == rds)
					return 1;
			}
			return 0;
		}
	}
}
void dfs(ll i) {
	if (can()) {
		ans = min(ans, i - 1);
	}
	if (i == n)
		return;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j && s[i] == 0 && s[j] == 0) {
				s[i] = 1, s[j] = 1;
				for (int r = 1; r <= n; r++)
					for (int s = 1; s <= n; s++)
						tmp[r][s] = edge[r][s];
				for (int r = 1; r <= n; r++)
					if (edge[i][r])
						edge[i][r] = 0, edge[j][r] = 1;
				for (int r = 1; r <= n; r++)
					if (edge[r][i])
						edge[r][i] = 0, edge[r][j] = 1;
				dfs(i + 1);
				for (int r = 1; r <= n; r++)
					for (int s = 1; s <= n; s++)
						edge[r][s] = tmp[r][s];
			}
}
void sol() {
	cin >> n >> m;
	ans = 6;
	memset(edge, 0, sizeof edge);
	for (int i = 1; i <= m; i++) {
		ll u, v;
		cin >> u >> v;
		edge[u][v] = 1;
	}
	dfs(1);
	cout << ans;
}
int main() {
//	freopen("circ.in","r",stdin);
//	freopen("circ.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	ll t;
	cin >> t;
	while (t--) {
		sol();
	}
	return 0;
}
/*
4
3 4
0 1
1 2
2 0
0 1
3 5
0 0
1 2
2 0
0 1
0 1
4 2
0 1
2 3
6 6
0 2
1 5
3 0
4 0
1 4
5 0
*/
